package com.lzq.leetcode.hoot100.ds;

import java.util.Arrays;

/**
 * 并查集解法
 */
public class s200 {

    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        UnionFind unionFind = new UnionFind(m, n);
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == '1') {
                    if (i+1 < m) {
                        unionFind.add(i, j, i+1, j);
                    }
                    if (j+1 < n) {
                        unionFind.add(i, j, i, j+1);
                    }
                }
            }
        }
        return unionFind.getRootNum();
    }

    public static class UnionFind {
        int[] arr;
        int m, n;

        UnionFind(int m, int n) {
            this.m = m;
            this.n = n;
            int size = m * n;
            arr = new int[size];
            Arrays.fill(arr, -2);
        }

        // 将两个节点合并为一个集合
        int add(int x1, int y1, int x2, int y2) {
            int pos1 = x1 * n + y1;
            int pos2 = x2 * n + y2;
            // 向上寻找
            int root = find(pos1);
            if (root == -2) arr[root] = -1;
            arr[pos2] = root;
            return root;
        }

        // 寻找根节点
        int find(int pos) {
            if (arr[pos] < 0) return pos;
            int root = find(arr[pos]);
            arr[pos] = root;
            return root;
        }

        int getRootNum() {
            int ans = 0;
            for (int e : arr) {
                if (e == -1) {
                    ++ans;
                }
            }
            return ans;
        }
    }
}
